package com.yjc.dp;

/**
 * 5. 最长回文子串
 *
 * @author yjc
 * @create 2024-07-25 10:31
 */
public class Subject_12 {
    public static void main(String[] args) {

        String s = "ac";
        int n = s.length();

        //最长子串长度
        int maxLen = 1;
        //子串起始坐标
        int begin = 0;

        if (n < 2) {
            System.out.println(s);
        }

        boolean[][] dp = new boolean[n + 1][n + 1];
        for (int i = 0; i < n; i++) {
            //一个字符时肯定为回文串
            dp[i][i] = true;
        }

        //枚举每个长度的回文子串
        for (int l = 2; l <= n; l++) {
            for (int i = 0; i < n; i++) {
                //子串尾坐标
                int j = l + i - 1;

                if (j >= n) {
                    break;
                }
                if (s.charAt(i) != s.charAt(j)) {
                    dp[i][j] = false;
                } else {
                    if (l < 3) {
                        dp[i][j] = true;
                    } else {
                        dp[i][j] = dp[i + 1][j - 1];
                    }
                }
                if (dp[i][j] && l > maxLen) {
                    maxLen = l;
                    begin = i;
                }
            }
        }
        System.out.println(s.substring(begin, begin + maxLen));


    }
}
